%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% This file is part of the book
%%
%% Probability and Its Applications
%% http://code.google.com/p/probability-book/
%%
%% Copyright (C) 2010 Minh Van Nguyen <nguyenminh2@gmail.com>
%%
%% See the file COPYING for copying conditions.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\dontprintsemicolon
%% data section
\SetKwInOut{Input}{Input}
\SetKwInOut{Output}{Output}
\SetKwData{False}{False}
\SetKwData{True}{True}
%% input/output
\Input{Two polynomials $F(x)$ and $G(x)$.}
\Output{\True if $F(x) \equiv G(x)$; \False otherwise.}
\BlankLine
%% algorithm body
$d \leftarrow$ maximum degree of $F(x)$ and $G(x)$\;
Choose an integer $r$ uniformly at random in the range
  $\{1, 2, \dots, 100d\}$\;
\eIf{$F(r) \neq G(r)$}{
  \Return \False\;
}{
  \Return \True\;
}
